NO.21 合并两个有序链表 简单
思路一：迭代法 这个题目也是学校老师讲述数据结构课程时说的。1. 创建一个新的头结点dummy，用prehead指针指向新创建的dummy头结点，用p指针指向l1链表的头结点，q指针指向l2链表的头结点。2. 比较p指向的节点的值和q指向的节点的值，如果p指向的节点值小，就让prehead的next指向p所指向的节点，然后prehead和p向后移动，反之就让prehead的next指向q所指向的节点，然后prehead和q向后移动。3. 直到p或者q指针有一个为null为止，最后检查p或者q是否有不为null的指针，如果有就让prehead指向非空的p或者q。返回dummy.next即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1==null)return l2;
if (l2==null)return l1;
ListNode dummy=new ListNode(0);
ListNode prehead=dummy,p=l1,q=l2;
while (p!=null&&q!=null){
if (p.val<q.val){
prehead.next=p;
prehead=prehead.next;
p=p.next;
}else {
prehead.next=q;
prehead=prehead.next;
q=q.next;
}
}
if (p!=null)prehead.next=p;
if (q!=null)prehead.next=q;
return dummy.next;
}
|
思路二：递归法 其实递归法不能算是第二个思路，只能说是思路一的另一种实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
if(l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
|
本人菜鸟，有错误请告知，感激不尽！
更多题解和学习记录博客:博客、github